package com.antg;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @author Antg
 * @date 2021/10/20  17:28
 */
public class Code_4 {
    public static void main(String[] args) {
        int a[] = {1,3};
        int b[] = {2};

        System.out.println(findMedianSortedArrays2(a,b));
    }

    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        //将两个数组合
        int tem[] = new int[nums1.length+nums2.length];
        System.arraycopy(nums1,0,tem,0,nums1.length);
        System.arraycopy(nums2,0,tem,nums1.length,nums2.length);
        //排序(冒泡)
        for(int i  = 0;i<tem.length;i++){
            for(int j = 0;j<tem.length-i-1;j++){
                if(tem[j]>tem[j+1]){
                    int t = tem[j];
                    tem[j] = tem[j+1];
                    tem[j+1] = t;
                }
            }
        }
        return (tem[(tem.length+1)/2-1]+tem[(tem.length+2)/2-1])/2.0;
    }

    public static double findMedianSortedArrays2(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        //将两个数组合
        int tem[] = new int[m+n];
        //判断哪个比较长就将哪个先放入容器(减少移动的次数)
        if(m>=n){
            //将num1放入容器
            System.arraycopy(nums1,0,tem,0,m);
            //将num2插入数组
            insert(tem,nums2,m-1,0);
        }else{
            //将num2放入容器
            System.arraycopy(nums2,0,tem,0,n);
            //将num1插入数组
            insert(tem,nums1,n-1,0);
        }
        return (tem[(tem.length+1)/2-1]+tem[(tem.length+2)/2-1])/2.0;
    }
    public static void insert(int[] container,int[] arr,int border,int start){
        if(start>arr.length-1){
            return;
        }
        //查找插入的位置
        int targetIndex = findIndex(container,arr[start],border);
        //将数值插入
            //末尾插入
        if(targetIndex==border+1){
            container[border+1] = arr[start];
            insert(container, arr, border+1, start+1);
//            System.out.println(container);
        }else{
            //其他位置插入
            int temp[] = Arrays.copyOfRange(container,targetIndex,border+1);
            //向后挪一位
            System.arraycopy(temp,0,container,targetIndex+1,temp.length);
            //插入目标值
            container[targetIndex] = arr[start];
            insert(container, arr, border+1, start+1);
        }
    }
    //使用二分法查找目标数字最接近数字的下标
    public static int findIndex(int[] arr,int target,int border){
        int high = border;
        if(target>arr[high]){
            return high+1;
        }
        int low = 0;
        int mid = 0;
        while(low<=high){
            mid = (low+high)/2;
            if(arr[mid]==target){
                return mid;
            }
            if(arr[mid]>target){
                high = mid-1;
            }
            if(arr[mid]<target){
                low = mid+1;
            }
        }
        return low>high?low:mid;
    }
}
